package com.tingyuge.base.structrue.heap;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class MaxHeap<E extends Comparable<E>> {
    private ArrayList<E> arrayList;

    public MaxHeap(int capacity) {
        this.arrayList = new ArrayList<>(capacity);
    }

    public MaxHeap(){arrayList  =  new ArrayList<>();}

    //返回堆中的元素

    public int getSize(){return arrayList.size();}

    public boolean isEmpty(){return arrayList.isEmpty();};

    //返回完全二叉堆中,父节点所在的索引
    public int parent(int index){
        if(index <=0){
            throw new IllegalArgumentException("argument error! ");
        }

        return (index-1)/2;
    }

    public int leftChild(int index ){
        return index * 2 +1;
    }

    //返回数组中 右孩子所在的索引
    public int rightChild(int index ){
        return index * 2 +2;
    }

    /**
     * 添加元数
     * @param e
     */
    public void add(E e){
        arrayList.add(e);
         siftUp(arrayList.size()-1);
    }

    /**
     * 1.将元素放在数组尾部,
     * 2.然后和他的父节点进行比较
     * 3.如果父节点比他小的话,俩个元素进行位置的对换
     * @param i
     */
    private void siftUp(int i) {
        //如果父节点的元数比添加的元素 小的话,进行交换
        while (i > 0 && arrayList.get(parent(i)).compareTo(arrayList.get(i)) < 0 ){
           swap(i,parent(i));
            i = parent(i);

        }
    }

    private void swap(int i ,int j){
        E e = arrayList.get(i);

        arrayList.set(i,arrayList.get(j));
        arrayList.set(j,e);
    }

    //查找最大的元素

    public E findMax(){
        if(arrayList.isEmpty()){
            throw new IllegalArgumentException("堆为空");
        };
        return arrayList.get(0);
    }

    //取出最大的元素
    public E extractMax(){
        E max = findMax();
//        arrayList.set(0,arrayList.get(arrayList.size()-1));
//        arrayList.remove(arrayList.size()-1);
        swap(0,arrayList.size()-1);
        arrayList.remove(arrayList.size()-1);
        siftDown(0);

        return max;
    }

    /**
     * 1.将最末尾的元素 放在首部
     * 2.将元素与左右孩子的值进行对比
     * @param index
     */
    private void siftDown(int index) {

        //如果左孩子的索引 < 长度的话
        while ( leftChild(index)< arrayList.size()){
            int k =leftChild(index) ;
            // data[index] 是左右孩子的最大值
            if(k+1 <arrayList.size() && arrayList.get(k+1).compareTo( arrayList.get(k) ) > 0 ){
               k++;

            }
            //父元素.>=0 的话就不需要交换了
            if(arrayList.get(index).compareTo(arrayList.get(k)) >= 0){
                break;
            }


            swap(index,k);
            index = k;


        }
    }



    public E replace(E e ){
        E max = findMax();
        arrayList.set(0,e);
        siftDown(0);
        return max;
    }

    public MaxHeap(List<E> arr){
        arrayList = new ArrayList<>(arr);
        for (int i = parent(arrayList.size()-1); i >=0  ; i--) {
            siftDown(i);
            
        }
    }

    /**
     * main..............
     * @param args
     */
    public static void main(String[] args) {

        int aaa = 100000;
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < aaa; i++) {
            int e = new Random().nextInt(Integer.MAX_VALUE);
        arrayList.add(e);

        }
        MaxHeap<Integer> maxHeap = new MaxHeap<>(arrayList);
        int[]  arr =new int[aaa];
        for (int i = 0; i <aaa ; i++) {
            arr[i] = maxHeap.extractMax();

        }

        for (int i = 1; i <aaa ; i++) {
            if(arr[i-1] <arr[i]){
                throw new IllegalArgumentException("错误...");
            }

        }
        System.out.println("MaxHeap.main");
    }


}